2479. Баланс скобок

Имеется строка, содержащая скобки () и []. Скобочное выражение считается правильным, если:

· оно является пустым

· если A и B правильны, то AB правильно

· если A правильно, то (A) и [A] правильны

Напишите программу, которая по входной строке, содержащей скобочное выражение, определит корректно ли оно. Длина строки не больше 128 символов.

Вход. Первая строка содержит количество тестов n. Каждая из следующих n строк содержит выражение, состоящее из скобок () и [].

Выход. Для каждого теста вывести в отдельной строке “Yes”, если выражение является правильным и “No” иначе.

Пример входа	Пример выхода
3 ([]) (([()]))) ([()[]()])()	Yes No Yes

РЕШЕНИЕ

структуры данных - стек

Анализ алгоритма

Для решения задачи будем использовать символьный стек. Будем двигаться последовательно по символам входной строки и:

· если текущий символ является открывающейся скобкой (круглой или квадратной), то заносим его в стек.

· если текущий символ является закрывающейся скобкой, то на вершине стека должна находиться соответствующая ему открывающаяся скобка. Если это не так, или если стек пуст, то скобочное выражение не является правильным.

По окончанию обработки правильной строки стек должен оказаться пустым.

Пример

Рассмотрим моделирование стека для строки “( ( [ ] ) [ ] )”.

Реализация алгоритма

Входное скобочное выражение будем читать в массив stroka. Объявим стек s, используемый в задаче.

char stroka[150];

stack<char> s;

Читаем количество тестов tests. Для каждой входной строки stroka вычисляем ее длину len. Переменная flag станет равной 1, если входное скобочное выражение не является правильным.

scanf("%d\n",&tests);

while(tests--)

{

gets(stroka); flag = 0;

Очищаем стек s.

while(!s.empty()) s.pop();

Двигаемся по символам входной строки stroka.

for(i = 0; i < strlen(stroka); i++)

{

Заносим в стек открывающуюся скобку.

if ((stroka[i] == '(') || (stroka[i] == '[')) s.push(stroka[i]);

Если текущий символ stroka[i] – закрывающаяся скобка, то выталкиваем символ из вершины стека, который должен быть соответствующей открывающейся скобкой. Если это не так, или если стек пуст, то устанавливаем flag равным 1.

else if (!s.empty() && ((stroka[i] == ')' && s.top() == '(') ||

(stroka[i] == ']' && s.top() == '['))) s.pop();

else flag = 1;

}

Если в конце обработки строки стек оказался не пустым, то входное скобочное выражение не является правильным.

if (!s.empty()) flag = 1;

В зависимости от значения переменной flag выводим ответ.

if (flag) printf("No\n"); else printf("Yes\n");

}

Java реализация

import java.util.*;

public class Main

{

static char rev(char c)

{

return (c == ')') ? '(' : '[';

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int tests = con.nextInt();

String Line = con.nextLine();

while(tests-- > 0)

{

Line = con.nextLine();

Stack<Character> s = new Stack<Character>();

int Flag = 0;

for(int i = 0; i < Line.length(); i++)

{

if (Flag > 0) break;

if ((Line.charAt(i) == '(') || (Line.charAt(i) == '['))

s.push(Line.charAt(i));

if ((Line.charAt(i) == ')') || (Line.charAt(i) == ']'))

{

if (s.empty() || (s.peek() != rev(Line.charAt(i))))

Flag = 1;

else s.pop();

}

}

if (!s.empty()) Flag = 1;

if (Flag > 0) System.out.println("No");

else System.out.println("Yes");

}

}

}